package primary.primary0;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

/**
 * 排序 + 双指针
 */
public class S0056合并区间 {


    /**
     * 97, 55，这个算法应该是没问题，就是数据结构用得有问题
     * 按照第一个字母排序之后，如果前一对的endi 比 starti+1要小，那么就是中断的。如果不是，比较endi 和 end i + 1的大小
     * 每个数字代表一个格子，这是个左闭右开的区间
     */
    public int[][] merge(int[][] intervals) {
        // 我不清楚为什么，但是从Comparator.comparingInt(o -> o[0])改写成自己手写comparator之后效率提高不少。
        // 总之注意，前减后就是从小到大，以这题为例子记住，以及记住这个函数式接口的匿名内部类实现
        // mark:Comparator
        Arrays.sort(intervals, new Comparator<int[]>() {
            public int compare(int[] array1, int[] array2) {
                return array1[0] - array2[0];
            }
        });
        // Arrays.sort(intervals, Comparator.comparingInt(o -> o[0]));

        List<int[]> res = new ArrayList<>();
        int[] curres = intervals[0];
        for (int[] interval : intervals) {
            if (interval[0] > curres[1]) {
                res.add(curres);
                curres = interval;
            } else {
                curres[1] = Math.max(curres[1], interval[1]);
            }
        }
        // 最后一个不能落了
        res.add(curres);
//        int[][] resArray = new int[res.size()][2];
//        for (int i = 0; i < res.size(); i++) {
//            resArray[i] = res.get(i);
//        }
//        return resArray;
        // mark: 这样写多好看，学一下这个List -> Array的转换
        // return res.toArray(new int[res.size()][]);

        // 离谱，这个传参只是为了带一个类型信息，
        return res.toArray(new int[0][0]);
    }
}
